import java.util.*;

class sudoku {
	public void solveSudoku(char[][] board) 
	{
	    ArrayList<int[]> moves = new ArrayList<int[]>();
	    for(int i = 0; i < board.length; i++)
	    {
	        for(int j = 0; j < board[0].length; j++)
	        {
	            if(board[i][j] == '.')
	            {
	                int[] r = {i,j};
	                moves.add(r);
	            }
	        }
	    }
	    finder(moves, board, 0);
	}
	public boolean finder(ArrayList<int[]> moves, char[][] board, int length)
	{
	    if(length >= moves.size())
	    {
	        return true;
	    }
	    int[] pos = moves.get(length);
	    boolean[] filles = new boolean[9];
	    for(int i = 0; i < filles.length; i++)
	    {
	        filles[i] = true;
	    }
	    //find possible moves
	    for(int i = 0; i < board.length; i++)
	    {
	        if(board[i][pos[1]] != '.')
	        {
	            int v = board[i][pos[1]] - '0';
	            filles[v-1] = false;
	        }
	    }
	    for(int i = 0; i < board[pos[0]].length; i++)
	    {
	        if(board[pos[0]][i] != '.')
	        {
	            int v = board[pos[0]][i] - '0';
	            filles[v-1] = false;
	        }
	    }
	    for(int i = 0 + (pos[0]/3) *3; i <= 2 + (pos[0]/3) *3; i++)
	    {
	         for(int j = 0 + (pos[1]/3) *3; j <= 2 + (pos[1]/3) *3; j++)
	         {
	             if(board[i][j] != '.')
	             {
	                 int v = board[i][j] - '0';
	                 filles[v-1] = false;
	             }
	         }
	    }
	    for(int i = 0; i < filles.length; i++)
	    {
	        if(filles[i])
	        {
	           board[pos[0]][pos[1]] = (char)((i+1)+'0');
	           boolean res = finder(moves, board,length+1);
	           if(res)
	            return true;
	           board[pos[0]][pos[1]] = '.';
	        }
	    }
	    return false;
	}
}

public class SudokuSolver {
	public void tester() {
		
//		char [][] p = {
//				{'5','3','.','.','7','.','.','.','.'},
//				{'6','.','.','1','9','5','.','.','.'},
//				{'.','9','8','.','.','.','.','6','.'},
//				{'8','.','.','.','6','.','.','.','3'},
//				{'4','.','.','8','.','3','.','.','1'},
//				{'7','.','.','.','2','.','.','.','6'},
//				{'.','6','.','.','.','.','2','8','.'},
//				{'.','.','.','4','1','9','.','.','5'},
//				{'.','.','.','.','8','.','.','7','9'}};
		
		char [][] p = {
				{'.','.','.','.','7','.','.','.','2'},
				{'.','.','.','1','9','5','.','.','8'},
				{'.','.','8','.','.','.','.','6','7'},
				{'.','.','.','.','6','.','.','.','3'},
				{'.','.','.','.','.','3','.','.','1'},
				{'.','.','.','.','2','.','.','.','6'},
				{'.','.','.','.','.','.','2','8','4'},
				{'.','.','.','.','.','9','.','.','5'},
				{'.','.','.','.','.','.','.','7','9'}};
		
//		(new sudoku()).solveSudoku(p);
		solveSudoku(p);
		
//		printCharA(p2);
	}
	
	public void printCharA(char [][]p) {
		System.out.println("-----------------");
		for(int i =0 ; i < 9 ; i ++) {
    		for(int j = 0 ; j < 9 ; j++) {
    			System.out.print(p[i][j]+" ");
    		}
    		System.out.println();
    	}
	}
	
    public void solveSudoku(char[][] board) {
        Stack <char[][]> st = new Stack <char[][]> ();
        
        st.push(board);
        while(! st.isEmpty()) {
        	char [][] p = st.pop();
        	
//        	System.out.println(isValid(p));
//        	printCharA(p);
        	
        	if(isValid(p)) {
        		if(hasDot(p)) {
            		addAllPossibleToSt(p, st);
            	}
            	else {
            		copy(board, p);
            		return;
            	}
        	}
        }
    }
    
    public void addAllPossibleToSt(char[][]p, Stack <char[][]> st) {
    	boolean [] t = new boolean [9];
    	
    	for(int i = 0 ; i < 9 ; i++) {
    		if(p[i][dotC] != '.')
    			t[p[i][dotC]-'1'] = true;
    		if(p[dotR][i] != '.')
    			t[p[dotR][i]-'1'] = true;
    	}
    	
    	int R = dotR/3;
    	int C = dotC/3;
    	
    	for(int i = R*3 ; i < R*3+3 ; i++) {
    		for(int j = C*3 ; j < C*3+3 ; j++) {
    			if(p[i][j] != '.')
        			t[p[i][j]-'1'] = true;
    		}
    	}
    	
    	for(char i = '1' ; i <= '9' ; i++) {
    		if(t[i-'1']) continue;
    		char [][] p2 = new char [9][9];
    		copy(p2, p);
    		p2[dotR][dotC] = i;
    		st.push(p2);
    		
    	}
    }
    
    public void copy(char [][] a, char [][]b) {
    	for(int i = 0 ; i < 9 ; i++) {
    		for(int j = 0 ; j < 9 ; j++) {
    			a[i][j] = b[i][j];
    		}
    	}
    }
    
    public boolean hasDot(char [][] b) {
    	
    	dotR = 0;
        dotC = 0;
        
    	for(int i =0 ; i < 9 ; i ++) {
    		for(int j = 0 ; j < 9 ; j++) {
    			if(b[i][j] == '.') {
    				dotR = i;
                	dotC = j;
                	// System.out.println(i+" "+j);
    				return true;
    			}
    		}
    	}
    	return false;
    }
    
    int dotR = 0, dotC = 0;
    
    public boolean isValid(char[][] board) {
        boolean [] t = new boolean [9];
        
        for(int i = 0 ; i < 9 ; i ++) {
            for(int j = 0 ; j < 9 ; j++) {
                if(board[i][j]!='.') {
                    if(t[board[i][j] - '1']) return false;
                    else t[board[i][j] - '1'] = true;
                }
            }
            clear(t);
        }
        
        for(int j = 0 ; j < 9 ; j ++) {
            for(int i = 0 ; i < 9 ; i++) {
                if(board[i][j]!='.') {
                    if(t[board[i][j] - '1']) return false;
                    else t[board[i][j] - '1'] = true;
                }
            }
            clear(t);
        }
        
        int [] a1 = {0,0,0,3,3,3,6,6,6};
        int [] a2 = {3,3,3,6,6,6,9,9,9};
        int [] b1 = {0,3,6,0,3,6,0,3,6};
        int [] b2 = {3,6,9,3,6,9,3,6,9};
        
        for(int k = 0 ; k < 9 ; k++) {
            for(int i = a1[k] ; i < a2[k] ; i++) {
                for(int j = b1[k] ; j < b2[k] ; j++) {
                    if(board[i][j]!='.') {
                        if(t[board[i][j] - '1']) return false;
                        else t[board[i][j] - '1'] = true;
                    }
                }
            }
            
            clear(t);
        }
        
        return true;
    }
    
    public void clear(boolean [] t) {
        for(int i = 0; i < 9 ; i++) {
            t[i] = false;
        }
    }
}